package LeetCode.leetcode45;

class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().jump(new int[]{2,1}));
    }
    public int jump(int[] nums) {
        int curIndex = 0;
        int curSteps = nums[0];
        int[] nextMaxSteps = new int[]{0,nums[0]};
        int res = 0;
        while (curIndex < nums.length - 1) {
            for (int i = curIndex + 1; i <= curIndex + curSteps; i++) {
                if (i >= nums.length) {break;}
                if (nums[i] + i > nextMaxSteps[0]+nextMaxSteps[1]) {
                    nextMaxSteps[0] = i;
                    nextMaxSteps[1] = nums[i];
                }
            }
            if (curIndex != nextMaxSteps[0]){
                res++;
            }
            curIndex = nextMaxSteps[0];
            curSteps = nextMaxSteps[1];
            if (curIndex + curSteps >= nums.length - 1) {
                return  res + 1;
            }

        }
        return res;
    }
}